package com.codebuffer.nowcoder;

import java.util.Arrays;
import java.util.PriorityQueue;

public class GetMedian {
    static PriorityQueue<Integer> minQueue = new PriorityQueue<>();
    static PriorityQueue<Integer> maxQueue = new PriorityQueue<>((o1, o2) -> o2-o1);
    static int count = 0;
    public static void Insert(Integer num) {
        if((count & 1) == 0){
            maxQueue.add(num);
            minQueue.add(maxQueue.poll());
        }else {
            minQueue.add(num);
            maxQueue.add(minQueue.poll());
        }
        count++;
    }

    public static Double GetMedian() {
        if((count & 1) == 0 ){
            return (maxQueue.peek()+minQueue.peek())/2.0;
        }else {
            return minQueue.peek()*1.0;
        }
    }

    public static void main(String[] args) {

        int arr[] = {5,2,3,4,1,6,7,0,8};
        for (int i = 0; i < arr.length; i++) {
            Insert(arr[i]);
            System.out.println(GetMedian());
        }

    }
}
